package DoubleLinkedLlist;

import SingleLinkList.MyLinklist;

public class MyLinkList implements DoubleLinkedList{

    static final class LinkNode{
        LinkNode next;       //前驱
        LinkNode prev;       // 后继
        int data;

        public LinkNode(int data) {
            this.data = data;
        }
    }

    //定义一个头尾节点
    public LinkNode head;
    public LinkNode last;



    @Override
    public void addFirst(int data) {
        LinkNode cur=new LinkNode(data);
        if(head==null){
            head=cur;
            last=cur;
            return ;
        }
        cur.next=head;
        head.prev=cur;
        head=cur;

    }

    @Override
    public void addLast(int data) {
        LinkNode cur=new LinkNode(data);
        if(head==null){
            head=cur;
            last=cur;
            return ;
        }
        last.next=cur;
        cur.prev=last;
        last=cur;
    }

    @Override
    public void addIndex(int index, int data) throws IndexIllegarlity {
        if(index<0 ||index>size()){
            throw new IndexIllegarlity(" index 异常");
        }

        LinkNode curNode=new LinkNode(data);
        LinkNode cur=head;

        if(index == 0){
            addFirst(data);
            return ;
        }

        if(index == this.size()){
            addLast(data);
            return ;
        }
        // 找index位置的节点
        while(index!=0){
            cur=cur.next;
            index--;
        }

        LinkNode curPrev=cur.prev;
        curPrev.next=curNode;
        curNode.next=cur;
        cur.prev=curNode;
        curNode.prev=curPrev;
    }

    @Override
    public boolean contains(int key) {
        /*  // 可以省略
        if(head==null){
            System.out.println(" 空链表，没有你要找的关键字");
            return false;
        }*/
        LinkNode cur=head;
        while(cur!=null){
            if(cur.data==key){
                return true;
            }
            cur=cur.next;
        }
        return false;
    }

    @Override
    public void remove(int key) {
        LinkNode cur=head;
        if(head==null){
            System.out.println(" 空链表，没有你要找的关键字");
            return ;
        }
/*      太复杂了，可以提炼到下面的while循环里面去
        if(head.data==key){
            LinkNode headNext=head.next;
            headNext.prev=null;
            head=headNext;
            return ;
        }
        if(last.data==key){
            LinkNode lastPrev=last.prev;
            lastPrev.next=null;
            last=lastPrev;
            return ;
        }
        while(cur!=null){
            LinkNode curPrev=cur.prev;
            LinkNode curNext=cur.next;
            if(cur.data == key){
                curPrev.next=curNext;
                curNext.prev=curPrev;
                return ;
            }
            cur=cur.next;
        }*/

        while(cur!=null){

            if(cur.data == key){
                // 说明是头节点
                if(cur==head){
                    head=head.next;
                    // 如果只有一个元素并且是我们要删除的元素时，head已经为空了
                    if(head!=null) {
                        head.prev = null;
                    }else{
                        last=null;
                    }

                }else{
                    //  不管是不是尾节点，都要执行下面操作
                    cur.prev.next=cur.next;
                    //  不是头节点 和 尾节点
                    if(cur!=last){
                        cur.next.prev=cur.prev;
                    }else {
                        last=last.prev;
                    }
                }

                return ;
            }
            cur=cur.next;
        }

    }

    @Override
    public void removeAllKey(int key) {
/*
        LinkNode cur=head;
        if(head==null){
            System.out.println(" 空链表，没有你要找的关键字");
            return ;
        }

        while(cur!=null){
            if(head.data==key){
                LinkNode headNext=head.next;
                headNext.prev=null;
                head=headNext;
                cur=cur.next;
                continue;
            }
            if(last.data==key){
                LinkNode lastPrev=last.prev;
                lastPrev.next=null;
                last=lastPrev;
                cur=cur.next;
                continue;
            }
            LinkNode curPrev=cur.prev;
            LinkNode curNext=cur.next;
            if(cur.data == key){
                curPrev.next=curNext;
                curNext.prev=curPrev;
            }
            cur=cur.next;
        }
*/


        LinkNode cur=head;
        if(head==null){
            System.out.println(" 空链表，没有你要找的关键字");
            return ;
        }
        while(cur!=null){

            if(cur.data == key){
                // 说明是头节点
                if(cur == head){
                    head=head.next;
                    if(head!=null) {
                        head.prev = null;
                    }else{
                        last=null;
                    }
                }else{
                    //  不管是不是尾节点，都要执行下面操作
                    cur.prev.next=cur.next;
                    //  不是头节点 和 尾节点
                    if(cur!=last){
                        cur.next.prev=cur.prev;
                    }else {
                        last=last.prev;
                    }
                }
            }
            cur=cur.next;
        }
    }

    @Override
    public int size() {
        LinkNode cur=head;
        int size=0;
        while(cur!=null){
            cur=cur.next;
            size++;
        }
        return size;
    }

    @Override
    public void display() {
        LinkNode cur=head;
        while(cur != null){
            System.out.print(cur.data+" -> ");
            cur=cur.next;
        }
        System.out.println(" null");
    }

    @Override
    public void clear() {
/*        // 直接将头尾节点置0: 不能回收所有节点
        head=null;
        last=null;

        */

        //遍历置零
        LinkNode cur=head;
        while(cur!=null){
            LinkNode curNext=cur.next;
            cur.next=null;
            cur.prev=null;
            cur=curNext;
        }
        last=null;
        head=null;
    }
}
